package 希尔排序;

import java.util.Arrays;

public class 希尔排序 {
	public static void main(String[] args) {
		//int[] arr = {8,9,1,7,2,3,5,4,6,0};
		//int[] arr = {2,5,3,4,1};
		//shellSortSwap(arr);	//交换法
		//shellSortMove(arr);		//移位法
		//System.out.println(Arrays.toString(arr));
		
		int[] longInt = new int[80000];
		for (int i = 0; i < longInt.length; i++) {
			longInt[i] = (int) (Math.random()*10000);
		}
		
		long star = System.currentTimeMillis();
		
//		shellSortSwap(longInt);		//交换法		8s
		shellSortMove(longInt);  	//移位法		25ms
		
		long end = System.currentTimeMillis();
		System.out.println((end-star) + "毫秒");
		System.out.println((end-star)/1000 + "秒");//2s
		
		
	}
	
	/**
	 * 希尔排序 ，移位式，里面使用插入排序
	 * 
	 * 移位式，是先比较数，找到合适位置再插入，省去交换式大量交换时间
	 * @param arr
	 */
	public static void shellSortMove(int[] arr) {
		
		int value = 0;
		int index = 0;
		for(int gap = arr.length/2 ; gap > 0 ; gap = gap/2) {
			
			//移位法是真正的插入排序
			for(int i = gap ; i < arr.length ; i++) {
				
				value = arr[i];
				index = i;
				
				if(arr[index] < arr[index-gap]) {
					while(index - gap >= 0 && value < arr[index-gap]) {
						arr[index] = arr[index-gap];
						index = index - gap;
					}
					//因为步长最小为1，所以从1 开始，最后index-gap == 1-1 ，在while中不是用
					//index判断的是用index-gap判断，所以while(index-gap)等于-1不通过，但是
					//index没变成-1，所以不用index+1
					arr[index] = value;
				}
				
			}
			
		}
	}
	
	
	/**
	 * 希尔排序，交换式，改进的插入排序，使用增量
	 * 
	 * 交换式类似冒泡，两两交换相邻的数，效率不高
	 * @param arr
	 */
	public static void shellSortSwap(int[] arr) {

		int temp = 0;
		for(int gap = arr.length/2 ; gap > 0 ; gap = gap/2) {
			
			//1.10个数，分成10/2=5组，步长为5，一共交换5次，所以从5开始
			for(int i = gap ; i < arr.length ; i++) {
				//2.j是从数组头开始，与距离一个增量的数交换，利用插入排序，如果一组中有多个数，
				//每次都是插入排序，当前数与前一个数比较，交换，数越多，趟数越多。
				for(int j = i - gap ; j >= 0 ; j = j - gap ) {
					if(arr[j] > arr[j + gap]) {
						//交换每一组中的数，利用步长 [0] 和 [0+5] , [1] 和 [1+5] ...
						temp = arr[j];
						arr[j] = arr[j+gap];
						arr[j+gap] = temp;
					}
				}
			}
		}
	}
}
